home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / std / c / 670 < prev    next >
Text File  |  1996-08-06  |  3KB  |  94 lines
  1. Path: lyra.csx.cam.ac.uk!jkb
  2. From: jkb@mrc-lmb.cam.ac.uk (James Bonfield)
  3. Newsgroups: comp.std.c
  4. Subject: Re: Restrictions on qsort compare function?
  5. Date: 29 Mar 1996 12:43:37 GMT
  6. Organization: MRC Laboratory of Molecular Biology, Cambridge UK
  7. Message-ID: <4jgltp$f9l@lyra.csx.cam.ac.uk>
  8. References: <4iokop$h4p@lyra.csx.cam.ac.uk> <4iqjar$2m9@usenet.pa.dec.com>
  9. NNTP-Posting-Host: alf2.mrc-lmb.cam.ac.uk
  10.  
  11. I now agree that non antisymmetric or nontransitive sort comparison functions
  12. are indeed invalid. I can see how this can be construed from the ansi
  13. standard, but can also see how it's possible to construe otherwise. In short
  14. it doesn't really state such things explicitly. Anyway, that aside I thought I
  15. should reply to the last note about this.
  16.  
  17. In article <4iqjar$2m9@usenet.pa.dec.com> diamond@tbj.dec.com (Norman Diamond) writes:
  18.  
  19. >>such functions appear to make [one implementation's] qsort() function
  20. >>underflow the passed array.
  21. >
  22. >This should not happen.
  23.  
  24. Well, that depends on whether or not you class qsorts behaviour as undefined
  25. for such functions.
  26.  
  27. >>#define NUM_ELE 10
  28. >>int main() {
  29. >>    int i;
  30. >>    int crashme;     /* removing this line fixes things! */
  31. >
  32. >This makes me suspicious that your test program is not exactly what you
  33. >posted, and your test program has a bug in some other part of its code
  34. >that already yielded undefined behavior.
  35.  
  36. Actually it's true - it does cause it to go wrong. I've got an example now
  37. that used explicitly defined numbers to cause a crash. With the crashme line
  38. in the program dies. Without it the program modifies memory not within the
  39. boundaries of qsort. My program is:
  40.  
  41. #include <stdio.h>
  42. #include <stdlib.h>
  43.  
  44. static int sort_func(const void *pa, const void *pb)
  45. {
  46.     const int *a = (int *)pa;
  47.     const int *b = (int *)pb;
  48.  
  49.     return *a > *b;
  50. }
  51.  
  52. #define NUM_ELE 10
  53. int main() {
  54.     int i;
  55.     int crashme;     /* removing this line fixes things! */
  56.     int sortme[NUM_ELE] = {148, 104, 126, 74, 108, 131, 129, 131, 125, 77};
  57.  
  58.     for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
  59.     putchar('\n');
  60.  
  61.     qsort((void *)(sortme+1), NUM_ELE-2, sizeof(int), sort_func);
  62.  
  63.     for (i=0; i<NUM_ELE; i++) printf("%d ", sortme[i]);
  64.     putchar('\n');
  65.  
  66.     return 0;
  67. }
  68.  
  69. >b < c and c < a).  As for whether qsort() is required to contend with
  70. >such nonsense, it "probably" isn't.
  71.  
  72. Agreed. Hence the above discoveries are most likely entirely within the realm
  73. of acceptability.
  74.  
  75. Perhaps the most interesting point to come out of this is the inefficiency of
  76. some qsort algorithms. Sorting 100,000 elements (with a "consistent" sort
  77. comparison function) gave the following approximations (ran several times with
  78. random input - of course these results may just reflect the random number
  79. generator woes!):
  80.  
  81. OSF/1 V3.0    ~72K
  82. Linux (gnu lib)    ~153K
  83. Irix 5.3    ~170K
  84. Solaris 5.3    ~305K
  85.  
  86. Thanks for all the suggestions everyone has made.
  87. Cheers,
  88.  
  89.     James
  90. --
  91. James Bonfield (jkb@mrc-lmb.cam.ac.uk)   Tel: 01223 402499   Fax: 01223 412282
  92. Medical Research Council - Laboratory of Molecular Biology,
  93. Hills Road, Cambridge, CB2 2QH, England.
  94.